//归并排序

// 核心思想：我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

const arr = [11, 8, 3, 9, 7, 1, 2, 5];

//  分
//  [11, 8, 3, 9, 7, 1, 2, 5]
//  [11,8,3,9] [7,1,2,5]
//  [11,8] [3,9] [7,1] [2,5]
//  [11] [8] [3] [9] [7] [1] [2] [5]
//  合
//  [8,11] [3,9] [1,7] [2,5]
//  [3,8,9,11] [1,2,5,7]
//  [1,2,3,5,7,8,9,11]

// 递推公式
// 递过去，归过来，分到最小值之后一层一层返回合并，
// 分解为子问题
// 找到出口是解决问题的关键

function merge_sort(arr) {
  if (arr.length === 1) {
    return arr;
  }
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid),
    right = arr.slice(mid, arr.length);
  return merge(merge_sort(left), merge_sort(right));
}

function merge(left, right) {
  let arr = [];
  while (left.length && right.length) {
    const leftValue = left[0],
      rightValue = right[0];
    if (leftValue < rightValue) {
      arr.push(leftValue);
      left.shift();
    } else {
      arr.push(rightValue);
      right.shift();
    }
  }
  if (left.length) {
    arr = arr.concat(left);
  } else {
    arr = arr.concat(right);
  }
  return arr;
}
